1978번 소수 찾기

Day9 9단계 20231026

풀이 1

• 에라토스테네스의 체 : 소수를 찾는 알고리즘

• https://ko.wikipedia.org/wiki/에라토스테네스의_체

  • 2부터 ~n까지 모든 수를 나열한다.
  • 2부터 자기 자신을 제외한 2의 배수를 모두 제거한다.
  • 남은 수 가운데 2 다음 수는 3이므로, 3부터 자기 자신을 제외한 3의 배수를 모두 제거한다.
  • 위 과정을 모두 반복하면 소수만 남는다.

• 위키피디아 java 코드

public class Eratos {
    public static void main(String[] args) {
        ArrayList<Boolean> primeList;
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        if(n <= 1) return;
        primeList = new ArrayList<Boolean>(n+1);
        primeList.add(false);
        primeList.add(false);
        for(int i=2; i<=n; i++ )
            primeList.add(i, true);
        for(int i=2; (i*i)<=n; i++){
            if(primeList.get(i)){
                for(int j = i*i; j<=n; j+=i) primeList.set(j, false);
            }
        }
        StringBuffer sb = new StringBuffer();
        sb.append("{");
        for(int i=0; i<=n; i++){
            if(primeList.get(i) == true){
                sb.append(i);
                sb.append(",");
            }
        }
        sb.setCharAt(sb.length()-1, '}');
        System.out.println(sb.toString());
    }
}

• 예시로 왜 소수가 아닌 수를 제거할 때 i*\i <= n을 사용하는지 확인해보자

  • 예시를 보면 처음 i = 2일 때, 2의 배수를 모두 지운다.
  • 2 다음 소수인 i = 3의 배수를 지우는 과정을 보면, 3*\3=9보다 작은 숫자들 중에서 특정 숫자들의 배수들은 이미 제거되었다.
  • 같은 과정을 반복하고 i =4일 때 4는 2의 배수를 지울 때 제거됬으므로 소수가 아니다.
  • i = 5일 때 5*\5=25 보다 작은 숫자들 중에서 특정 숫자들의 배수인 수들은 이미 제거되었다.
  • 따라서 i가 증가할수록 이전 i-1일 때의 숫자의 배수들을 모두 지운 결과 i*\i 보다 작은 숫자들은 모두 소수이므로 i*\i보다 큰 숫자들이 소수인지 판별하면 된다.

• 내 풀이

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		if (n == 1) { return; }
		
		int[] nums = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < n; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		// making custom Eratosthenes set(from wikipedia)
		List<Boolean> eratos = new ArrayList<>();
		eratos.add(0, false); eratos.add(1, false); // 0과 1은 소수가 아님
		for (int i = 2; i <= 1000; i++) {
			eratos.add(i, true); // 먼저 모든 수를 소수라고 생각하고 true
		}
		for (int i = 2; i*i <= 1000; i++) { // i보다 작은 수의 배수는 i-1 처리 과정에서 삭제
			if (eratos.get(i)) {
				for (int j = i*i; j <= 1000; j+=i) { //i*i에서 i를 더하면 계속 i의 배수가 된다
					eratos.set(j, false); // 소수 아닌 수 제거
				}
			}
		}

		int count = 0;
		for(int i : nums) {
			if(eratos.get(i)) { count++; }
		}
		System.out.println(count);
		br.close();
	}
}

풀이 2

• 풀이 날짜 : 2025.05.22
• 약 1년 만에 부트 캠프에서 문제를 풀면서 다시 풀게 되었다.
• 이번엔 소수를 찾는 방법 중 에라토스테네스의 체가 아닌 소수 판별을 할 숫자의 제곱근 이하의 정수들 중 약수가 있는지 판별하는 방법을 사용했다.
• 어떤 수의 약수들은 그 수의 제곱근을 기준으로 대칭형으로 분배되어 있기에 제곱근보다 작은 정수들 중에 약수가 만약 존재한다면 그 수는 소수가 아니다.
• 문제에서 주어진 숫자들을 위 방법으로 소수 판별하고, 소수인 숫자들을 ArrayList에 저장하여 ArrayList의 길이를 최종 반환한다.

import java.io.*;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        BufferedReader reader;
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            int size = Integer.parseInt(reader.readLine());
            String[] lines = reader.readLine().split(" ");
            ArrayList<Integer> primality = new ArrayList<>();
            loop: for(int i = 0; i < size; i++) {
                int target = Integer.parseInt(lines[i]);
                if (target == 1) continue;
                int sqrt = (int) Math.sqrt(target);
                for (int j = 2; j <= sqrt; j++) {
                    if (target % j == 0) continue loop;
                }
                primality.add(target);
            }
            System.out.println(primality.size());

        } catch (Exception e) {
        }
    }
}